package com.lql.AVLTree;


/**
 * 实现平衡二叉树
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {4, 3, 6, 5, 7, 8};
        AVLTree aVLTree = new AVLTree();
        for (int j : arr) {
            AVLTreeNode aVLTreeNode = new AVLTreeNode(j);
            aVLTree.addNode(aVLTreeNode);
        }
        aVLTree.listBSTTree();
        System.out.println("_________________");
        System.out.println(aVLTree.height());
        System.out.println(aVLTree.leftHeight());
        System.out.println(aVLTree.rightHeight());
    }
}

/**
 * 管理二叉排序树
 */
class AVLTree {
    private AVLTreeNode root;//根节点

    /**
     * 返回根节点
     *
     * @return 根节点
     */
    public AVLTreeNode getRoot() {
        return root;
    }

    public void setRoot(AVLTreeNode root) {
        this.root = root;
    }

    /**
     * 添加节点
     *
     * @param node 待添加节点
     */
    public void addNode(AVLTreeNode node) {
        if (root == null) {
            //空树
            root = node;
            return;
        }
        root.addNode(node);
    }

    /**
     * 遍历树
     */
    public void listBSTTree() {
        if (root == null) {
            //空树
            System.out.println("树为空，无法遍历");
            return;
        }
        root.listBSTTree();
    }

    /**
     * 查找节点
     *
     * @param value 节点value值
     * @return 找到则返回当前节点，否则返回空
     */
    public AVLTreeNode finNode(int value) {
        if (root == null) {
            //空树
            System.out.println("树为空，查找失败");
        }
        return root.finNode(value);
    }

    /**
     * 查找指定节点的父节点
     *
     * @param value 待查找节点的value值
     * @return 返回待查找节点的父节点
     */
    public AVLTreeNode findParentNode(int value) {
        if (root == null) {
            //空树
            System.out.println("树为空，父节点查找失败");
        }

        return root.findParentNode(value);
    }

    /**
     * 删除节点
     *
     * @param value 待删除结点的值
     */
    public void delNode(int value) {
        if (root == null) {
            //空树
            System.out.println("树为空，删除失败");
        }
        if (root.value == value) {
            //待删除节点为根节点
            if (root.leftNode == null && root.rightNode == null) {
                //只有一个根节点
                root = null;
                return;
            } else if (root.leftNode != null && root.rightNode != null) {
                //左右子树都存在
                root.delNode(value);
            } else {
                //除根节点，只存在一个节点
                if (root.leftNode != null) {
                    //左子树存在
                    root = root.leftNode;
                } else {
                    root = root.rightNode;
                }
            }
            return;
        }
        root.delNode(value);
    }

    /**
     * 返回左子树的高度
     *
     * @return 左子树的高度
     */
    public int leftHeight() {
        if (root == null || root.leftNode == null) {
            //空树
            return 0;
        }
        return root.leftNode.height();
    }

    /**
     * 返回右子树的高度
     *
     * @return 右子树的高度
     */
    public int rightHeight() {
        if (root == null || root.rightNode == null) {
            //空树
            return 0;
        }
        return root.rightNode.height();
    }

    /**
     * 返回树的高度
     *
     * @return 树的高度
     */
    public int height() {
        if (root == null) {
            //空树
            return 0;
        }
        return root.height();
    }
}

/**
 * 平衡二叉树的节点类
 */
class AVLTreeNode {
    public int value;//表示是节点中存储的节点信息
    public AVLTreeNode leftNode;//左节点
    public AVLTreeNode rightNode;//右节点

    public AVLTreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "AVLTreeNode{" +
                "value=" + value +
                '}';
    }

    /**
     * 返回左子树的高度
     *
     * @return 左子树的高度
     */
    public int leftHeight() {
        return this.leftNode == null ? 0 : this.leftNode.height();
    }

    /**
     * 返回右子树的高度
     *
     * @return 右子树的高度
     */
    public int rightHeight() {
        return this.rightNode == null ? 0 : this.rightNode.height();
    }

    /**
     * 返回树的高度
     *
     * @return 树的高度
     */
    public int height() {
        return Math.max(this.leftNode == null ? 0 : this.leftNode.height(),
                this.rightNode == null ? 0 : this.rightNode.height()) + 1;
    }

    /**
     * 二叉排序中添加节点
     *
     * @param node 待添加的节点
     */
    public void addNode(AVLTreeNode node) {
        if (node == null) {
            System.out.println("节点为空，无法添加");
            return;
        }
        if (node.value < this.value) {
            //待添加的节点值小于当前节点，添加到左子树上
            if (this.leftNode == null) {
                //左子树为空，直接添加
                this.leftNode = node;
                return;
            }
            //不为空则直接递归左子树，添加节点
            this.leftNode.addNode(node);
        } else {
            //待添加的节点值小于等于当前节点，添加到右子树上
            if (this.rightNode == null) {
                //右子树为空，直接添加
                this.rightNode = node;
                return;
            }
            //不为空则直接递归右子树，添加节点
            this.rightNode.addNode(node);
        }

        //当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
        if (rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if (rightNode != null && rightNode.leftHeight() > rightNode.rightHeight()) {
                //先对右子结点进行右旋转
                rightNode.rightRotate();
                //然后在对当前结点进行左旋转
            }
            //直接进行左旋转即可
            leftRotate(); //左旋转..
            return; //必须要!!!
        }

        //当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
        if (leftHeight() - rightHeight() > 1) {
            //如果它的左子树的右子树高度大于它的左子树的高度
            if (leftNode != null && leftNode.rightHeight() > leftNode.leftHeight()) {
                //先对当前结点的左结点(左子树)->左旋转
                leftNode.leftRotate();
                //再对当前结点进行右旋转
            }
            //直接进行右旋转即可
            rightRotate();
        }
    }

    /**
     * 左旋转
     */
    //左旋转方法
    private void leftRotate() {
        //创建新的结点，以当前根结点的值
        AVLTreeNode newNode = new AVLTreeNode(value);
        //把新的结点的左子树设置成当前结点的左子树
        newNode.leftNode = leftNode;
        //把新的结点的右子树设置成带你过去结点的右子树的左子树
        newNode.rightNode = rightNode.leftNode;
        //把当前结点的值替换成右子结点的值
        value = rightNode.value;
        //把当前结点的右子树设置成当前结点右子树的右子树
        rightNode = rightNode.rightNode;
        //把当前结点的左子树(左子结点)设置成新的结点
        leftNode = newNode;
    }

    /**
     * 右旋转
     */
    //右旋转
    private void rightRotate() {
        AVLTreeNode newNode = new AVLTreeNode(value);
        newNode.rightNode = rightNode;
        newNode.leftNode = leftNode.rightNode;
        value = leftNode.value;
        leftNode = leftNode.leftNode;
        rightNode = newNode;
    }

    /**
     * 中遍历显示排序二叉树
     */
    public void listBSTTree() {
        if (this.leftNode != null) {
            //递归左子树
            this.leftNode.listBSTTree();
        }
        System.out.println(this.value);
        if (this.rightNode != null) {
            //递归右子树
            this.rightNode.listBSTTree();
        }
    }

    /**
     * 查找节点
     *
     * @param value 节点value值
     * @return 找到则返回当前节点，否则返回空
     */
    public AVLTreeNode finNode(int value) {
        if (this.value == value) {
            return this;
        }
        if (this.value > value) {
            //递归左子树
            if (this.leftNode != null) {
                //左递归查找
                return this.leftNode.finNode(value);
            } else {
                //左子树为空,未找到
                return null;
            }
        } else {
            //递归右子树
            if (this.rightNode != null) {
                //右递归查找
                return this.rightNode.finNode(value);
            } else {
                //右子树为空,未找到
                return null;
            }
        }
    }

    /**
     * 查找指定节点的父节点
     *
     * @param value 待查找节点的value值
     * @return 返回待查找节点的父节点
     */
    public AVLTreeNode findParentNode(int value) {
        if ((this.leftNode != null && this.leftNode.value == value) ||
                (this.rightNode != null && this.rightNode.value == value)) {
            return this;
        } else {
            if (this.value > value && this.leftNode != null) {
                //左递归查找
                return this.leftNode.findParentNode(value);
            } else if (this.value <= value && this.rightNode != null) {
                //右递归查找
                return this.rightNode.findParentNode(value);
            } else {
                //左右节点都为空，只存在根节点
                return null;
            }
        }
    }

    /**
     * 删除左子树上最大值并返回最大值
     *
     * @param node 节点
     * @return 左子树上的最大值
     */
    public int delLeftMaxNode(AVLTreeNode node) {
        //获取当前节点的左子树
        AVLTreeNode leftNode = node.leftNode;
        //遍历左子树的右子树的最右节点，即为最大值
        while (leftNode.rightNode != null) {
            leftNode = leftNode.rightNode;
        }
        //删除左子树上的最大节点
        delNode(leftNode.value);
        //返回被删除节点的值
        return leftNode.value;
    }

    /**
     * 删除节点
     *
     * @param value 待删除结点的值
     */
    public void delNode(int value) {
        //当前节点
        AVLTreeNode AVLTreeNode = finNode(value);
        //父节点
        AVLTreeNode parentNode = findParentNode(value);
        if (AVLTreeNode == null) {
            //未找到待删除结点
            return;
        }
        if (AVLTreeNode.leftNode == null && AVLTreeNode.rightNode == null) {
            //待删除节点为叶子节点
            if (parentNode.leftNode == AVLTreeNode) {
                //待删除结点为左节点
                parentNode.leftNode = null;
            }
            if (parentNode.rightNode == AVLTreeNode) {
                //待删除结点为右节点
                parentNode.rightNode = null;
            }
        } else if (AVLTreeNode.leftNode != null && AVLTreeNode.rightNode != null) {
            //左右子树都存在
            AVLTreeNode.value = delLeftMaxNode(AVLTreeNode);
        } else {
            //左右子树只存在一个
            if (AVLTreeNode.leftNode != null) {
                //左子树存在
                if (parentNode.leftNode == AVLTreeNode) {
                    //待删除结点为父节点的左子树
                    parentNode.leftNode = AVLTreeNode.leftNode;
                }
                if (parentNode.rightNode == AVLTreeNode) {
                    //待删除结点为父节点的右子树
                    parentNode.rightNode = AVLTreeNode.leftNode;
                }
            } else {
                //右子树存在
                if (parentNode.leftNode == AVLTreeNode) {
                    //待删除结点为父节点的左子树
                    parentNode.leftNode = AVLTreeNode.rightNode;
                }
                if (parentNode.rightNode == AVLTreeNode) {
                    //待删除结点为父节点的右子树
                    parentNode.rightNode = AVLTreeNode.rightNode;
                }
            }
        }
    }
}